package 剑指offer;

import java.util.LinkedList;
import java.util.Queue;

public class _13机器人的运动范围 {
	public static void main(String[] args) {
		System.out.println(movingCount1(38,15,9));
		System.out.println(bfs(38,15,9));
	}
	/**
	 * 
	 *@time 2020年12月21日下午7:14:48
	 * 
	 *@param m
	 *@param n
	 *@param k
	 *@return int
	 *
	 *@see 递推求解
	 */
	  public static  int movingCount(int m, int n, int k) {
		  if(k==0) {
			  return 1;
		  }
		boolean vis[][]=new boolean[m][n];
		int ans=1;
		vis[0][0]=true;
		for (int i = 0; i <m; i++) {
			for (int j = 0; j <n; j++) {
				if(i==0&&j==0||get(i)+get(j)>k) 
					continue;
				if(i-1>=0&&!vis[i][j])
				vis[i][j]=vis[i-1][j];
				if(j-1>=0&&!vis[i][j])
				vis[i][j]=vis[i][j-1];
				ans+=vis[i][j]? 1:0;
			}			
		}
		return ans;	    
	  }
	  /**
	   * 
	   *@time 2020年12月21日下午8:55:58
	   * 
	   *@param m
	   *@param n
	   *@param k
	   *@return int
	   *
	   *@see DFS （Deepth First Search）广度优先算法
	   */
	  
	  public static  int movingCount1(int m, int n, int k) {
		  if(k==0) return 1;
		  boolean vis[][]=new boolean[m][n];
		 return dfs(m, n, 0, 0, vis, k);		  
	  }
	  /**
	   * 
	   *@time 2020年12月21日下午9:05:55
	   * int 
	   *
	   *@see 深度优先
	   */
	  public static int dfs(int m,int n,int i,int j,boolean vis[][],int k) {
		 if(i>=m||j>=n||get(i)+get(j)>k||vis[i][j])
			 return 0;
		 vis[i][j]=true;
		 return 1+dfs(m, n, i+1, j, vis, k)+dfs(m, n, i, j+1, vis, k);
	  }
	  /**
	   * 
	   *@time 2020年12月21日下午9:29:30
	   * 
	   *@param m
	   *@param n
	   *@param k
	   *@return int
	   *
	   *@see 广度优先
	   */
	  public static int bfs(int m,int n,int k) {
		if(k==0) return 1;
		int ans=0;
		boolean vis[][]=new boolean[m][n];
		Queue<Integer[]> queue=new LinkedList<Integer[]>();
		queue.offer(new Integer[] {0,0});
		int x,y;
		while (!queue.isEmpty()) {
		Integer[] cell= queue.poll();
		x=cell[0];  y=cell[1];
		if(x>=m||y>=n||get(x)+get(y)>k||vis[x][y]) continue;
		vis[x][y]=true;
		ans++;
		queue.offer(new Integer[] {x+1,y});
		queue.offer(new Integer[] {x,y+1});
		}
		  return ans;
		  
	  }
	  public static int get(int n) {
		  int res=0;
		  while(n!=0) {
			  res+=n%10;
			  n/=10;
		  }
		  return res;
		  
	  }

}
